An online map service can provide virtual maps to one or more mobile devices. The virtual maps can include point of interests (POIs). A POI can be a place that is designated as useful or of interest to a user. For example, a POI can be a shop, restaurant, or a hotel. Each POI may have an address (e.g., a street address). To display a POI in a virtual map, the online map service can geocode the POI, including determining a location (e.g., latitude and longitude coordinates) of the POI. An exemplary technique of geocoding is address interpolation. Upon determining the latitude and longitude coordinates of the address of the POI, the online map service can display a marker representing the POI on the virtual map at the latitude and longitude coordinates.